package com.jxb.three;

import com.jxb.first.ListNode;

/**
 * 重排链表
 *  * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *  *  L0 → L1 → … → Ln-1 → Ln
 *  * 请将其重新排列后变为：
 *  * L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
 *  * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * @author jiaobo
 * @date Created in 2024/12/29 17:25
 **/
public class ReorderList_143 {

    public static void main(String[] args) {

    }

    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        //找出中间节点(双指针)
        ListNode f = head;
        ListNode s = head;
        while (f.next != null && f.next.next != null) {
            f = f.next.next;
            s = s.next;
        }

        //对后半部分节点进行反转
        //指定三个指针进行反转，preMiddle，preCurrent，current
        //preMiddle是中间节点
        //preCurrent是中间节点的下一个节点
        //current是中间节点的next，next
        //进行循环遍历，
        //  current = preCurrent.next;
        //  preCurrent.next = current.next;
        //  current.next =preMiddle.next;
        //  preMiddle.next = current
        ListNode preMiddle = s;
        ListNode preCurrent=s.next;
        while (preCurrent.next != null) {
            ListNode current = preCurrent.next;
            preCurrent.next = current.next;
            current.next = preMiddle.next;
            preMiddle.next = current;
        }

        //以”梅花间隔“的方式将反转后的链表插入到前半部分链表
        //使用快慢指针和中间节点指针(s,f,p)
        //进行遍历，条件slow!=preMiddle
        //  1:p.next = f.next;
        //  2:f.next = s.next;
        //  3:s.next = f;
        //  4:s = f.next;
        //  5:f = preMiddle.next;
        s = head;
        f = preMiddle.next;
        while (s != preMiddle) {
            preMiddle.next = f.next;
            f.next = s.next;
            s.next = f;
            s = f.next;
            f = preMiddle.next;
        }
    }

}
